#include "../bulk_storage/bulk_storage.h"

/**
 \defgroup Query 

 Indices, query handlers, and interfaces to allow extensions.
*/

/**
 \defgroup QueryHandlers Query Handlers

 Callback functions that allow for filtering, storage and other treatment of query results.

 The query handler callback interface is as follows.  This
 documentation describes the default usage.  See the documentation of
 the Query Handler's sub-modules for more detailed information about
 the meaning of these parameters:

 @param data The first parameter is a void pointer to data.  Usually
 this is a pointer to a struct that matched the current query.  The
 caller (usually an index's query function) may free this pointer after the
 callback function returns.

 @param state The second parameter is a void pointer to state
 information.  The state information is defined by the implementor of
 the query handler callback, and is usually the pointer passed into
 the state parameter of a query function.

 @return Query handlers return a void pointer.  This pointer is
 discarded by the index's query function, but is used by complex query
 handlers.  For maximum reusability, query handlers should return 0 if
 the query hit is to be discarded, or return the data pointer if the
 hit is to be kept.  (The pointer may be freed regardless of the
 return value.)

 Before attempting to implement your own query handlers, be sure to read the documentation for the following modules:

 @see QueryFilter QueryConverter QueryResultSet ComplexQueryHandler

 \ingroup Query
*/

/**
 \defgroup Indices

 Implementations of data indices.  Currently, B-Tree and M-Tree are available.  Both implementations are backed by store structures, and can be manipulated in-memory, or on-disk

 \ingroup Query

*/

/**
   This is used by filterAnd (and soon some other filters) to store 
   the query handlers that will be executed when a query hit occurs.
*/

/** 
 * \defgroup QueryResultSet Result Sets
 * Functions to store or output query results.
 *
 * In order to store query results, these query handlers must make a
 * physical copy of the data that was returned by the index.  This is
 * because the index will free any memory that is passes into a query
 * handler.  Also, in memory intensive applications, it may be better
 * to do all processing and output of query results in query handlers,
 * so that your program does not have to keep a physical copy of the
 * data in memory.  
 *
 * Of course, there are situations where this is not feasible.
 * Therefore, the query result set module was created.
 *
 * \ingroup QueryHandlers
 */
/**
 * \defgroup QueryFilter Filters
 * Boolean functions to filter query results.
 *
 * When used within a ComplexQueryHandler, these filters allow
 * complicated queries to be created relatively easily.  Query filters
 * are just standard query handlers that return 0 when they evaluate
 * to false, and return their data parameter when they evaluate
 * to true.
 *
 * Like any other query handler, filters take a state parameter that
 * is defined by the implementor, and instantiated by the caller.
 *
 * \ingroup QueryHandlers
 */
/**
 * \defgroup ComplexQueryHandler Complex Queries
 *
 * Complex queries can be created by using complex query handlers.
 * These query handlers generally take a filter_state struct as their
 * state parameter.  They apply the functions in this structure to
 * their data parameter, starting at the beginning of the array.  
 *
 * The exact behavior at this point depends on which complex query
 * handler is being used.  A complex query handler checks the return
 * value of each function it calls, and interprets a return value of
 * zero (null) as false, and any other value as true.  Generally, the
 * query handler will use a non-null return value as a new data
 * parameter for further processing, so filters always should return
 * their data parameter or null.  The experimental QueryConverter
 * module's documentation has more information about how to conver
 * query result data within a query handler.
 *
 * \ingroup QueryHandlers
 */
/**
 * \defgroup QueryConverter
 *
 * The idea of a query converter is still experimental and no
 * implementations currently exist.  There are cases where a query
 * returns one data type, but another data type would be more
 * convenient to work with.  A query converter generates new structs
 * or objects from query results.  There are some unresolved problems
 * with memory management, since the query converter will return
 * before its output is used.  Therefore, it would be up to a later
 * portion of the query to call free() on the pointer, but this adds
 * unnecessary complexity to the downstream filters (which shouldn't
 * care about memory management at all).  The best solution so far is
 * to create a 'converter adaptor' that would call the QueryConverter,
 * call another Query handler with the output of the converter, and
 * then call free() on the output of the converter.  It could check
 * for null pointers from the converter, and stop processing of the
 * current query hit if one is encountered.
 *
 * \ingroup QueryHandlers
 */
/** 
 * \defgroup Fpredicate Predicate calculus
 * \ingroup QueryHandlers
 */

/** 
    Structure used to support filterAnd, or any other query handler
    that runs a list of query handlers on query results.
    
    \ingroup ComplexQueryHandler
*/

struct filter_state {
  /** Number of functions to map. */
  int count;  
  /** Function pointers. */
  void * (**functions)(void *, void *);
  /** States for each function. */
  void ** states;
};
/** 
    Passes input into the first function in s.  If that function
    returns null (0), then processing stops.  Otherwise, the value
    that it returns is passed into the next function in s.  This
    continues until the last function in s has been executed, or one
    of the functions returns 0.
    
    Each function in s is treated as a query handler.  The
    corresponding state data from s will be passed in accordingly.

    Effectively, this implements a logical and.  You may rely on the
    calling order of the functions in s.  This allows for query
    optimization, and production of query handlers that convert data
    from one type to another.

    Note that arbitrarily complex query handlers can be created by
    following the query handler interface, and the following conventions:

    1) When one query handler (a) calls another query handler (b), it
       is the responsibility of (a) to produce (b)'s state parameter.

    2) 'Filter' query handlers implement boolean functions, and return
       0 if the test fails (is false), or the pointer passed into
       their data parameter if the test succedes (is true).

    4) When a query handler (a) requires a different data type than is
       being returned by the query, a 'converter' query handler (b) could
       be used to create temporary objects that (a) can handle.  This
       would cause a memory management problem, as (b) would return
       before (a) used (b)'s return value.  On the other hand, (a)
       wouldn't know that it should free (b)'s pointer, so a special
       mechanism would have to be developed to ensure that the
       temporary value is properly freed.

    @todo Implement a filterOr, and a filterNot.

    @todo Move the interface discussion from filterAnd's documentation
          to it's own module (named Filter?)

  \ingroup ComplexQueryHandlers
*/
void* filterAnd(void * input, struct filter_state * s);

/**
 *  This struct carries the state data needed to support a k-nearest
 *  neighbor filter.  The most interesting fields are queryObject,
 *  results, and results_distance.  queryObject is the object that
 *  everything is compared to.  You may safely change it while the
 *  knn_state is empty.  (Either after a call to knn_state_alloc or to
 *  knn_state_reset).  Results contains k slots for result objects.
 *  To distinguish empty (garbage) slots from used slots, check the
 *  corresponding slot in results_distance.  A value of MAXDOUBLE in
 *  results_distance indicates that the slot is empty.
 */
struct knn_state {
  void   * queryObject;
  /** sizeof() the structure that's being returned... */
  size_t   result_size;
  /** These aren't really chars!  Assuming sizeof(char) == 1, we can
      do proper pointer arithmetic on it... */
  char   * results;     
  double * results_distance;
  /** The distance function.  (Almost always the one given to the indexing structure.) */
  double (*distance)(const void *, const void*);
  /** The total capacity of this state struct.  */
  int k; 
  /** Caches the object furthest from query_object.  (The next one
   *  to be replaced...)  max_dist will be -1 if there is no cached
   *  object.
   */
  double max_dist;
  /** The internal index of the object referred to by max_pos */
  int max_pos;
};

// ---------------------  KNN Stuff ---------------------------

/**
 *  Stores the k nearest results in *(knn_state.results)
 *
 *  This is O(k * #number of hits).  It could be faster, but that
 *  would require more code, so I haven't bothered yet.  (This was
 *  written for k ~=5, so it's not a big deal...In fact, it seems to
 *  scale quite well in practice.)
 *
 *  @return A null pointer if the result was discarded, result
 *  otherwise.  This allows knn to conform to the interface expected
 *  by query_handler wrappers.
 *
 *  \ingroup QueryResultSet
 */ 
void* knn(void * result, struct knn_state * s);

/**
   Allocates a knn state object with all the necessary fields.  It's here to reduce the number of errors on the part of our callers.
*/
struct knn_state * knn_state_alloc(int k, void * queryObject, double(*distance)(const void *, const void *), size_t result_size);

/**
 *  Resets the contents of the knn_state so that it can be re-used without executing malloc...
 */
void knn_state_reset(struct knn_state * s);
/** 
    Frees the memory being used by s.
*/
void knn_state_free(struct knn_state* s);

void knn_state_print(struct knn_state * s, void(*printObj)(void*,void*));


// ---------------------  Count hits Stuff ---------------------------


/**
 *  This query handler increments hit_count each time it is called,
 *  providing a count of the number of hits a query returns.
 *  hit_count should be set to zero before the query is run.
 *  \ingroup QueryHandlers
*/
void* count_hits(void * result, off_t * hit_count);


void knn_state_free(struct knn_state* s);
void* knn(void * result, struct knn_state * s);


/** 
 * Used in condition tests of the form \f$\{p|d(p) \in \mathbf{R}\}\f$
 * r0, r1 must be the same type as the r parameter of d.
 * \ingroup Fpredicate
 */
struct dstate{
  /** \brief Strong condition state data. */
  void* r0;

  /** \brief Weak condition state data. */
  void* r1;

  /** \brief State data. (Origin, etc.) */
  void* p0;

  /** \brief Results of the query */
  void* results;

  /** \brief Number of elements in results. */
  size_t n;

  /** \brief sizeof(QueryObject) */
  size_t qSize;

  /** \brief sizeof(Condition state data)  */
  size_t rSize;

  /** \brief sizeof(State data)  */
  size_t pSize;
  /** 
   * \brief The predicate r0, r1 apply to. 
   *
   * d is a mapping function. In general we want to test whether d(p)
   * satisfies r0 or r1, so d(p) might be trivial.
   * \param p0 - State data necessary for application of d to p
   * \param p - The element we wish to test.
   *
   * \return A void pointer compatable with the dp paramiter in the
   * membership function in.
   **/
  double (*d)(void* p0, const void* p);


  /** 
   * \brief Set membership test. (DOXYGEN HATES THIS MEMBER.)
   *
   * Applies the membership test. Think if it as the part of a 
   * set statement that comes after the epsilon.
   * \param p0 - State data necessary for testing if dp is a member of
   * thoses elements that satisfy condition r.
   * \param dp - The result of d(p).
   * \param r - State data that specifies the set to test for membership on.
   *
   * \return dp if \f$d(p) \in r$\f. -1 otherwise. 
   **/
  double (*in)(void* p0, double dp, const void* r);


};

/** 
 * Cast class. Defines the members necessary to work with the 
 * radius_test predicate.
 * \ingroup Fpredicate
 */
struct dpoint{
  double dist;
};


/** 
 * Allocates the dpoints to make d.r0, r1 usable.
 * 
 * @param d The dstate to initialize.
 */
void dstate_alloc_dpoint(struct dstate* d);

/**
 * Tests to see if p satisfies the weak condition.
 * \f$\{p | d(p) \in r_0 \cup r_1\}\f$
 * \see dstate
 * 
 * \return null if the condition is not satisfied, p otherwise.
 * \ingroup Fpredicate 
 */
void* filter_weak_cond(void* p, const void* state);


/**
 * Tests to see if p satisfies the strong condition.
 * \f$\{p | d(p) \in r_0 \cap r_1\}\f$
 * \see dstate
 * 
 * \return null if the condition is not satisfied, p otherwise.
 * \ingroup Fpredicate 
 */
void* filter_strong_cond(void* p, const void* state);


/** 
 * \brief Tests to see if dp->dist is within r->dist.
 * 
 * \param p0 - Origin state data. Unused.
 * \param dp - Distance from the origin. Has member: dist.
 * \param r - Test radius. Has member dist.
 * 
 * \return dp if dp->dist <= r->dist. 0 otherwise.
 * \ingroup Fpredicate
 */
double radius_test(void* p0, double dp, const void* r);


/** 
 * Write any structure to a bulk_store.
 * 
 * \param obj - The struct to write out.
 * \param s - The store to write to.
 *
 * \return obj
 * \ingroup QueryResultSet
 */
const void* store_add(const void* obj, struct store* const s);


struct print_with_distance_state {
  const void * query_object;
  double (*distance)(const void *, const void*);
  const void * (*print)(const void *, void*);
  void * print_state1;
  void * print_state2;
};

/**
 * 
 * 
 *
 *
 */
const void* print_with_distance(const void* obj, struct print_with_distance_state* s);

